package LeetCode1;

/**
 * 寻找两个正序数组的中位数O(log(m+n))
 * 快排
 * @author 是阿秋啊
 * @date 2022/03/31 16:28
 **/
public class Num4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        int[] ret = new int[len];
        for (int i = 0; i < len; i++) {
            if (i < nums1.length) {
                ret[i] = nums1[i];
            } else {
                ret[i] = nums2[i - nums1.length];
            }
        }
        helperSort(ret,0,ret.length - 1);
        double number;
        if (len % 2 == 0) {
             number = (double) (ret[(len - 1 )/ 2] + ret[len / 2]) / 2;
        } else {
            number = (double) (ret[len / 2]);
        }
        return number;
    }

    private void helperSort(int[] ret, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition(ret,l,r);
        helperSort(ret, l, p - 1);
        helperSort(ret, p + 1, r);
    }

    private int partition(int[] ret, int l, int r) {
        int v = ret[l];
        int i = l;
        int j = l + 1;
        while (j <= r) {
            if (ret[j] > v) {
                swap(ret,j,i + 1);
                i++;
            }
            j++;
        }
        swap(ret,l,i);
        return i;
    }

    private void swap(int[] ret, int j, int i) {
        int temp = ret[j];
        ret[j] = ret[i];
        ret[i] = temp;
    }
}
